Back to course home
0% completed
Vote For New Content
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Data Structures and Complexity Analysis
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Practical Applications and Case Studies
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Quadratic Time: O(n²)
Quadratic Time Complexity
Key Characteristics
In an algorithm with
- The runtime increases quadratically as the input size grows.
- This complexity is often seen in algorithms where each element is compared with every other element, such as certain sorting algorithms.
Code Example
Here’s an example of an
Java
. . . .
- Explanation: In the
has_duplicatesmethod, the outer loop iterates through each element, while the inner loop checks every other element after it. For each element inarr, we compare it with every subsequent element.
- Why
? If arrhaselements, the outer loop runs times, and for each iteration of the outer loop, the inner loop runs up to times. This results in roughly comparisons, giving a time complexity of .
Examples of operations
- Bubble Sort or Selection Sort: Sorting algorithms like bubble sort compare each element with others, making them
in time complexity. - Checking for Duplicate Pairs: In a scenario where you need to check all pairs of items in a list, such as finding all pairs with a specific difference, the process takes quadratic time.
- Distance Calculation Between Points: If you’re calculating distances between each pair of points in a 2D space, the time taken grows quadratically with the number of points.
Linear Time: O(n)
Quiz
Mark as Completed
On this page
Key Characteristics
Code Example
Examples of